package com.example.leetcode.tree;

import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreeUtils;

/**
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
 * 输出：3
 * 解释：和等于 8 的路径有 3 条，如图所示。
 * 示例 2：
 *
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：3
 *
 *
 * 提示:
 *
 * 二叉树的节点个数的范围是 [0,1000]
 * -109 <= Node.val <= 109
 * -1000 <= targetSum <= 1000
 */
public class leetcode437 {
    public static void main(String[] args) {
        Integer[] root = {10, 5, -3, 3, 2, null, 11, 3, -2, null, 1};
        int targetSum = 8;
        TreeNode node = TreeUtils.generateLeetcodeTree(root);

        Solution solution = new Solution();
        int sum = solution.pathSum(node, targetSum);
        System.out.println(sum);
    }

    static class Solution {
        /**
         * 遍历整棵树每个节点	枚举所有起点情况
         */
        public int pathSum(TreeNode root, int targetSum) {
            // 主函数：从每个节点出发，尝试找所有从该节点出发的路径总和为 targetSum
            if (root == null) return 0;

            // 1. 从当前节点出发，找符合条件的路径数量
            int fromRoot = dfs(root, targetSum);

            // 2. 递归左子树和右子树，分别以它们为起点再去找
            // 尝试以左右子树为起点的路径
            int fromLeft = pathSum(root.left, targetSum);
            int fromRight = pathSum(root.right, targetSum);

            // 3. 返回总路径数量
            return fromRoot + fromLeft + fromRight;
        }

        /**
         * 固定当前节点为起点	找从一个节点出发的路径
         * 该函数尝试从当前节点向下递归，查找路径总和为 targetSum 的路径数
         */
        private int dfs(TreeNode node, long targetSum) {
            if (node == null) return 0;

            int count = 0;

            // 如果当前节点值等于目标值，则找到一个路径
            if (node.val == targetSum) {
                count++;
            }

            // 继续向下递归左右子节点，减去当前节点值后的目标值
            // 从左右子树分别搜索下方的路径
            count += dfs(node.left, targetSum - node.val);
            count += dfs(node.right, targetSum - node.val);

            // 符合条件的路径数量
            return count;
        }
    }


}
